package done.easy_501_600;

import org.junit.Test;

import static com.study.util.LogUtil.info;
import static java.lang.Math.max;

/**
 * 581. Shortest Unsorted Continuous Subarray 最短无序连续子数组
 * <p>
 * 给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升
 * 序排序，那么整个数组都会变为升序排序。
 * 你找到的子数组应是最短的，请输出它的长度。
 * <p>
 * 示例 1:
 * 输入: [2, 6, 4, 8, 10, 9, 15]
 * 输出: 5
 * 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
 * <p>
 * 解决方案：
 * 原始数组: nums
 * [2, 6, 4, 8, 10, 9, 15]
 * <p>
 * 首先排序: sortNums
 * [2, 4, 6, 8, 9, 10, 15]
 * <p>
 * 定义两个指针
 * i-->            <--j
 * <p>
 * NO.1 首先 i++
 * 当 nums[i] != sortNums[j] 的时候，说明找到了开始节点
 * <p>
 * NO.2 然后 j--
 * 当 nums[j] != sortNums[j] 的时候，说明找到了结束节点
 * <p>
 * [2, 4, 6, 8, 9, 10, 15]
 * <p>
 * i++
 * [2, 6 ................]
 * <p>
 * j--
 * [................9, 15]
 * <p>
 * 此时，原数组中 6->9 这一段需要重新排序
 * <p>
 * [... 4, 6, 8, 9, 10...]
 *
 * @author 大硕
 * 2019-04-09 9:29 AM
 **/
@SuppressWarnings("all")
public class ShortestUnsortedContinuousSubarray {

    public int findUnsortedSubarray(int[] nums) {
        // 190409 first
        return -1;
    }

    @Test
    public void test() {
        info(findUnsortedSubarray(new int[]{2, 6, 4, 8, 10, 9, 15}));
    }
}













































/*
public int findUnsortedSubarray(int[] nums) {
    int n = nums.length;
    int[] a = Arrays.copyOf(nums, n);

    Arrays.sort(a);

    int min;
    int max;

    // 从左向右遍历
    for (min = 0; min < n; min++) {
        if (a[min] != nums[min])
            break;
    }

    // 从右向左遍历
    for (max = n-1; max >= 0; max--) {
        if (a[max] != nums[max])
            break;
    }

    return max(max - min + 1,0);
}
*/
